package fun.coding.leetcode;

public class InsertionSortList {

	public static void main(String[] args) {
		InsertionSortList instance = new InsertionSortList();
		int[] a1 = {2, 3, 1, 4};
		ListNode res1 = instance.insertionSortList(LeetCodeHelpers.buildLinkedList(a1));
		LeetCodeHelpers.printList(res1);
	}
	
	// dummy 
	// 2 3 1 4
	public ListNode insertionSortList(ListNode head) {
		ListNode dummyHead = new ListNode(-1);
		
		while (head != null) {
			ListNode next = head.next;
			ListNode cur = dummyHead.next;
			ListNode pre = dummyHead;
			// this is not very standard insertion implementation
			while (cur != null) {
				if (head.val < cur.val) {
					pre.next = head;
					head.next = cur;
					break;
				}
				
				pre = cur;
				cur = cur.next;
			}
			if (cur == null) {
				pre.next = head;
				head.next = null;
			}
			head = next;
		}
		
		return dummyHead.next;
	}
	
	/* 
	 // very good implementation
	 // dummy 
	 // 2 3 1 4
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);

        while (head != null) {
            ListNode node = dummy;
            while (node.next != null && node.next.val < head.val) {
                node = node.next;
            }
            ListNode temp = head.next;
            head.next = node.next;
            node.next = head;
            head = temp;
        }

        return dummy.next;
    }
    */
}
